1. Field of the Invention
The present invention relates to routing packets in a communication network, and, more particularly, to scheduling routing of packets through nodes of the network to guarantee a data transfer rates and delay bounds between data sources and destinations.
2. Description of the Related Art
Packet networks, such as asynchronous transfer mode (ATM) networks, commonly schedule processing and forwarding of data packets (or xe2x80x9ccellsxe2x80x9d in ATM networks) received at each intermediate node. Such scheduling may be employed to reduce or prevent excessive delay experienced by packets of each user""s data connection, termed a virtual circuit connection (VC-connection), as the packets are routed through the node. Scheduling allows network providers to guarantee data transfer rates and bounds for delay through the node and the network. Network providers may then offer these rates and bounds for the VC-connections as a guaranteed service. Minimizing implementation costs for a per-virtual-circuit connection (per VC-connection) scheduling algorithm is a performance objective for designers of packet networks. Such algorithms for scheduling packets may achieve excellent delay and fairness properties by approximating an ideal scheduling discipline, known as a Generalized Processor Sharing (GPS) scheduling algorithm. One exemplary GPS scheduling algorithm is described in A. K. Parekh and R. G. Gallagher, xe2x80x9cA Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case,xe2x80x9d IEEE/ACM Trans. Networking, pp. 344-357, June 1993 (hereinafter xe2x80x9cParekhxe2x80x9d).
Among GPS scheduling algorithms used by a scheduler of the node, the class of packet-by-packet rate-proportional servers (P-RPS) is known in the art for near optimal delay properties. The schedulers of this class compute, for each packet, or group of packets, queued in the node, a xe2x80x9ctimestampxe2x80x9d value (the timestamp is also known as the xe2x80x9cvirtual finishing timexe2x80x9d). The timestamp specifies when the packet(s) should be routed (transmitted) relative to packet(s) of the other VC-connections in the node. Several such P-RPS scheduling algorithms well-known in the art are: Packet-by-packet Generalized Processor Sharing (P-GPS), Virtual Clock, Frame-based Fair Queuing (FFQ), Self-Clocked Fair Queuing (SCFQ), and Starting-Potential Fair Queuing (SPFQ). These algorithms differ in the specific measure or function used as the system potential (predefined service time reference that may be calculated on an ongoing basis) to compute the timestamps. These algorithms are described in, for example, Parekh; D. Stiliadis and A. Varma, xe2x80x9cDesign and Analysis of Frame-based Fair Queuing: A New Traffic Scheduling Algorithm for Packet-Switched Networks,xe2x80x9d Proc. SIGMETRICS ""96, pp. 104-115, May 1996; L. Zhang, xe2x80x9cVirtual Clock A New Traffic Control Algorithm for Packet Switching,xe2x80x9d ACM Trans. Comp. Syst., pp.101-124, May 1991; D. Stiliadis and A.Varma, xe2x80x9cEfficient Fair Queuing Algorithms for ATM and Packet Networks,xe2x80x9d Tech. Rep. UCSC-CRL-95-59, December 1995; and S. J. Golestani, xe2x80x9cA Self-Clocked Fair Queuing Scheme for Broadband Applications,xe2x80x9d Proc. INFOCOM ""94, pp. 636-646, April 1994 (hereinafter xe2x80x9cGolestanixe2x80x9d).
In addition to delay properties, another measure of scheduling algorithm performance is the xe2x80x9cfairnessxe2x80x9d of the scheduling discipline. Fairness is generally used to characterize the priority or distribution of delay that the scheduler assigns to servicing packet(s) of each connection in the queues when the node is backlogged (i.e., when the queues are not empty while servicing or completing service of a connection). Two measures of fairness are commonly employed in the art. The first fairness measure is the service fairness index (SFI, described in Golestani) that measures the distance (as mathematically defined, such as the Euclidean distance) of the particular scheduling discipline from the ideal fairness of GPS in distributing service to VC-connections that are simultaneously backlogged.
The second fairness measure is the worst-case fairness index (WFI) that measures the maximum amount of time that packets of a backlogged VC-connection may have to wait between two consecutive services (e.g., processing and routing of two separately received groups of packets). WFI is described in J. C. R. Bennett and H. Zhang, xe2x80x9cWF2Q: Worst-case Fair Weighted Fair Queueing,xe2x80x9d Proc. INFOCOM ""96, pp. 120-128, March, 1996. Schedulers with minimal WFI are known in the art as worst-case-fair schedulers and are desirable, since the distribution of service to competing connections in a scheduler with small WFI is much less bursty than in a scheduler with a large WFI.
A P-RPS worst-case fair scheduler may employ xe2x80x9csmallest eligible virtual finishing time firstxe2x80x9d (SEFF) packet-selection. With SEFF, the scheduler grants the next service to the packet of a VC-connection having the minimum timestamp among those packets satisfying an xe2x80x9celigibility condition.xe2x80x9d The eligibility condition may be that the packet of a VC-connection have a starting potential (or virtual starting time) that is not greater than the current value of system potential. For each VC-connection, the eligibility condition needs to be verified only for the packet at the head of the corresponding queue, since this is the packet with the minimum starting potential among all packets in that queue. Depending on the specific P-RPS algorithm employed, the scheduler with SEFF selection may be work-conserving (e.g., P-GPS and SPFQ algorithms) or non-work-conserving (e.g., Virtual Clock and FFQ algorithms). A P-RPS scheduler employing SEFF selection may have optimal delay bounds, be worst-case fair, and have an SFI close to the theoretical lower bound in packet-by-packet servers. SEFF selection is described in J. C. R. Bennett and H. Zhang, xe2x80x9cHierarchical Packet Fair Queueing Algorithms,xe2x80x9d Proc. SIGCOMM ""96, pp. 143-156, August 1996; and D. Stiliadis and A. Varma, xe2x80x9cA General Methodology for Designing Efficient Traffic Scheduling and Shaping Algorithms,xe2x80x9d Proc. INFOCOM ""97, April 1997.
Four factors contribute to a total implementation cost for a P-RPS worst-case fair scheduler. The first factor is the complexity of calculating or maintaining the system potential, which factor is generally specific to the particular scheduling algorithm (e.g., for a scheduler supporting V VC-connections, this complexity is O(V) for the P-GPS algorithm, O(logV) for the SPFQ algorithm, and O(1) in Virtual Clock and FFQ algorithms, where O(*) is the mathematical relation xe2x80x9con the order of *xe2x80x9d) The other three factors, common to all P-RPS worst-case fair schedulers, are: (i) the complexity of identifying the eligible packets, (ii) the cost of handling and storing the timestamps, and (iii) the complexity of sorting the timestamps of the eligible packets in order to select the one with minimum timestamp for the next service. The complexity of implementing SEFF is a considerable burden when the scheduler""s implementation is based on conventional priority queues, since a worst-case of O(V) packets may become eligible for service at the same time.
Discrete-rate scheduling may be used instead of conventional priority queues when the scheduler is only required to support a relatively small discrete set of guaranteed service rates at any time. In the discrete-rate scheduler, backlogged VC-connections with the same service rate are grouped together in a First-In-First-Out (FIFO) rate queue, and only packets for VC-connections at the head of each FIFO rate queue are scheduled for service. Thus, the number of VC-connections for which the eligibility condition must be determined and the number of corresponding timestamps to be sorted are significantly reduced (equal to the number of supported service rates). Consequently, the complexity of implementing the SEFF policy is considerably decreased. In the case of P-RPS worst-case fair schedulers, discrete-rate scheduling yields negligible degradation in delay bounds when compared to conventional priority queues, and conserves both the minimal WFI and the excellent SFI of conventional priority queues.
While discrete-rate scheduling reduces implementation complexity of P-RPS worst-case fair schedulers, discrete-rate scheduling still requires computing and storing a timestamp for each connection, which is a significant contribution to the implementation cost of the scheduler. This method of prior art discrete-rate scheduling is referred to herein as xe2x80x9cdiscrete-rate scheduling with per-connection timestampsxe2x80x9d. Such discrete-rate scheduling technique is described in J. C. R. Bennett, D. C. Stephens, and H. Zhang, xe2x80x9cHigh Speed, Scaleable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks,xe2x80x9d Proc. ICNP ""97, pp. 7-14, October 1997. To further reduce implementation complexity, a discrete-rate scheduler may not compute and store a timestamp for each connection, but maintains a single timestamp per service rate. While this method of discrete-rate scheduling without per-connection timestamps achieves near-optimal delay bounds, the service fairness index is significantly compromised. Such scheduling is described in F. M. Chiussi and A. Francini, xe2x80x9cImplementing Fair Queueing in ATM Switches: The Discrete-Rate Approach,xe2x80x9d Proc. INFOCOM ""98, pp. 272-281, March 1998.
In accordance with the present invention, single-bit-timestamp discrete-rate scheduling distributes service to competing connections (e.g., packet connections such as virtual-circuit connections) using a single bit per connection, rather than using a multi-bit timestamp for each connection. One of a plurality of connections received by a server in a packet network is selected for service and updated in the following manner. Each connection is assigned to a corresponding rate queue based on a service rate of the connection, each rate queue having a corresponding queue timestamp and a queue bit. Each connection is assigned a connection bit. The connection, if any, at a head of a rate queue is selected for service based on the queue timestamp of the rate queue, the queue timestamp satisfying a predetermined criterion. The connection is dequeued by i) removing the connection selected for service from the corresponding rate queue, and by ii) updating at least one of the corresponding queue timestamp, queue bit, and connection bit of the connection. The connection is enqueued by i) appending the connection to the tail of the corresponding rate queue, and ii) updating at least one of the corresponding queue timestamp, queue bit, and connection bit of the connection. Single-bit timestamp discrete-rate scheduling may achieve the same delay bounds and fairness indices of the discrete-rate scheduling using a multi-bit timestamp for each connection, and may allow a network provider to guarantee data transfer rates and delay bounds between data sources and destinations.